package com.techyuan.algorithm.sorts.select;

import com.techyuan.algorithm.sorts.InsertionSort;
import com.techyuan.algorithm.utils.SortUtils;


/**
 * Created by tianjuntao on 2016/12/16.
 */
public class BFPRTSelect implements ISelect {
    private static InsertionSort insertionSort = new InsertionSort();

    public int select(int[] data, int i) {
        return bfprtSelect(data, 0, data.length - 1, i);
    }

    /**
     * @param data  数组
     * @param start 开始位置
     * @param end   结束位置
     * @param k     第k个元素
     * @return
     */
    private int bfprtSelect(int[] data, int start, int end, int k) {
        if ((end - start + 1) <= 5) {
            int[] tmpArr = insertionSort.sort(data);
            return tmpArr[start + k - 1];
        }

        int mid = getArrayMid(data, start, end); //mid 为中位数 id
        int m = SortUtils.partition(data, start, end, mid), cur = m - start + 1;
        if (k == cur) return data[m];  //刚好是第k个数
        else if (k < cur) return bfprtSelect(data, start, m - 1, k);//第k个数在左边
        else return bfprtSelect(data, m + 1, end, k - cur);         //第k个数在右边
    }

    public static int getArrayMid(int[] data, int start, int end) { //l,r均为数组下标 , 返回中位数的位置
        if (start == end) {
            return start;
        }
        int i = start;
        for (; i <= end - start - 5; i += 5) {// 子数组的元素个数为 5 个时
            insertionSort.sort(data, i, i + 4); //对当前的五个数数进行排序
            SortUtils.swap(data, start + (i - start) / 5, i + 2); //将所有中位数放在数组 array 的前几位上
        }
        if (i < end - start) {
            insertionSort.sort(data, i, end - start);
            SortUtils.swap(data, start + (i - start) / 5, (i + end - start) / 2); //将最后一组数的中位数放在数组 array 的前几位上
        }
        return getArrayMid(data, start, start + (i - start) / 5); // 返回中位数的中位数的 id
    }
}
